
struct ListNode
{
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};
#include <vector>
#include<algorithm>

class Solution
{
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    bool isPail(ListNode *head)
    {
        // write code here
        // 找到链表中间节点 ，断开为两个链表
        if (head == nullptr || head->next == nullptr)
            return true;
        // ListNode *pre = nullptr;
        ListNode *slow = head;
        ListNode *fast = head;
        ListNode *reverse_head = nullptr;
        while (fast != nullptr && fast->next != nullptr)
        {
            // pre = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        // if (pre != nullptr)
        //     pre->next = nullptr;

        reverse_head = reverseList(slow);
        // 2.逐元素比较 有不同返回false
        while (head != nullptr && reverse_head != nullptr)
        {
            if (head->val != reverse_head->val)
            {
                return false;
            }
            head = head->next;
            reverse_head = reverse_head->next;
        }
        return true;
    }
    ListNode *reverseList(ListNode *head)
    {
        if (head == nullptr || head->next == nullptr)
            return head;
        ListNode *pre = nullptr;
        ListNode *cur = head;
        ListNode *tempnext = nullptr;
        while (cur)
        {
            tempnext = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tempnext;
        }
        return pre;
    }

    // ================利用数组======================
    bool isPail2(ListNode *head){
        std::vector<int> nums;
        while(head){
            nums.push_back(head->val);
            head = head->next;
        }
        std::vector<int> temp = nums;
        // 反转数组
        std::reverse(temp.begin(),temp.end());
        for(int i=0;i<nums.size();i++)
        {
            if(nums[i]!=temp[i]){
                return false;
            }
        }
        return true;
    }
};